################################################################################
# Model Evaluation & ROC curve                                                 #
# ref : machine learning with R, CH 10                                         #
# ref : https://www.r-bloggers.com/a-small-introduction-to-the-rocr-package/   #
# ref : https://www.r-bloggers.com/illustrated-guide-to-roc-and-auc/           #
################################################################################

################################################################################
# terms                                                                        #
# TP FN TF FP                                                                  #
# recall , precison , accuracy , error rate                                    #
# Sensitivity , Specifity                                                      #
# Kappa Stat                                                                   #
# F measure                                                                    #
# roc curve , auc                                                              #  
# cross validation                                                             #
################################################################################

################################################################################
# package & methods                                                            #
# CrossTable in gmodels package                                                # 
# confusionMatrix in caret package                                             #
# createFolds in caret package                                                 #
# ROCR package                                                                 #
################################################################################
#0. 기본적인 model evaluation 에 쓰이는 지표들은 위와 같다.
# 서비스에서 탐지하려는 것이 어떤 것인가에 따라, 모델의 성능을 평가하는 척도도 달라지기 마련인데, 
# 기본적으로 confusion matrix 의 네가지 값의 조합으로 만들어진다.
#1. prediction 결과 Data Frame 
# success : 실제 성공 여부 값 
# prob    : 성공할확률 예측값
# predict : threshold 0.6 을 기준으로, threshold 값보다 크면 성공이라고 판단한 최종 예측값 
head(result)
#1.1 기초적인 Accuracy , Precision, Recall 을 구해보자 ( + Sensitivity , Specificity )
evaluate_model <- function(df) {
  a <- filter(df, predict == 1 & success == 1)
  b <- filter(df, predict == 0 & success == 1)
  c <- filter(df, predict == 0 & success == 0)
  d <- filter(df, predict == 1 & success == 0)
  
  success_precision <- nrow(a) / (nrow(a) + nrow(d)) 
  success_recall    <- nrow(a) / (nrow(a) + nrow(b)) 
  fail_precision    <- nrow(c) / (nrow(b) + nrow(c)) 
  fail_recall       <- nrow(c) / (nrow(c) + nrow(d))  
  accuracy          <- (nrow(a) + nrow(c)) / nrow(df)
  
  evaluation_result <- as.data.frame(list(
    `success_precision` = success_precision, 
    `success_recall` = success_recall, 
    `fail_precision` = fail_precision,  
    `fail_recall` = fail_recall, 
    `accuracy` = accuracy
  ))
  
  return(evaluation_result)
}
print(evaluate_model(result))
# precision 과 recall 앞에 success / fail 이라는 prefix 가 있다. 
# 예측모델에서 주안점을 둬서, 탐지해 내야할 대상이 success 이냐 fail 이냐에 따라서 달라질 수 있다는 이야기인데, 
# 위의 confusion matrix 의 기준이 Actually Spam 이냐 Acutally Ham 이냐의 차이이다. 

#1.2  직접 구현을 해서 기초 평가 지표를 뽑았으나, 라이브러리를 사용해도 된다.
library(gmodels)
CrossTable(result$success, result$predict)

 
   Cell Contents
|-------------------------|
|                       N |
| Chi-square contribution |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  88908 

 
               | result$predict 
result$success |         0 |         1 | Row Total | 
---------------|-----------|-----------|-----------|
             0 |     24344 |     13500 |     37844 | 
               |  3779.282 |  2908.251 |           | 
               |     0.643 |     0.357 |     0.426 | 
               |     0.630 |     0.269 |           | 
               |     0.274 |     0.152 |           | 
---------------|-----------|-----------|-----------|
             1 |     14320 |     36744 |     51064 | 
               |  2800.861 |  2155.332 |           | 
               |     0.280 |     0.720 |     0.574 | 
               |     0.370 |     0.731 |           | 
               |     0.161 |     0.413 |           | 
---------------|-----------|-----------|-----------|
  Column Total |     38664 |     50244 |     88908 | 
               |     0.435 |     0.565 |           | 
---------------|-----------|-----------|-----------|

 
library(caret)
confusionMatrix(result$predict, result$success)
Confusion Matrix and Statistics

          Reference
Prediction     0     1
         0 24344 14320
         1 13500 36744
                                         
               Accuracy : 0.6871         
                 95% CI : (0.684, 0.6901)
    No Information Rate : 0.5743         
    P-Value [Acc > NIR] : < 2.2e-16      
                                         
                  Kappa : 0.3618         
 Mcnemar's Test P-Value : 9.095e-07      
                                         
            Sensitivity : 0.6433         
            Specificity : 0.7196         
         Pos Pred Value : 0.6296         
         Neg Pred Value : 0.7313         
             Prevalence : 0.4257         
         Detection Rate : 0.2738         
   Detection Prevalence : 0.4349         
      Balanced Accuracy : 0.6814         
                                         
       'Positive' Class : 0              
                                         
# 1.3 개별적인 지표들은 이제 살펴봤다. 
# 그러니까, precision / recall / sensitivity / specificity 와 Precision 과 Recall 의 산술평균'스러운' Accuracy 까지
# 아직 안 본 것이 F-measure 인데, 위의 식을 보면 조화 평균(harmonic mean) 을 사용하고 있다. 

# F-measure 는 각각 표현되는 두개의 값 precision 과 recall 을 combine 하여 나타내기 위한 것이다.
# 산식은 간단하고, 높으면 대체적으로 precision 과 recall 이 모두 우수하다는 것을 말한다.

# 하지만 왜? 산술 평균 말고 조화 평균인가?
# ref : http://www.4four.us/article/2013/09/how-to-combine-two-values
# 위의 그림과 링크에서 설명되듯이, 
# precision , recall 중 한쪽이 지나치게 나쁜 경우 
# ex> 실제 데이터의 실패:성공 = 0.99:0.01 인 경우, 성공을 예측하는 경우 recall 은 굉장히 좋은 반면 precision 이 엉망일 수 있다.
# 이 경우, accuracy 를 통해 평가를 하면 도드라지지 않지만, f-measure 를 하면 값이 일정 수준 이상 올라갈 수가 없다.
# 주의 : 모든 경우에 accuracy / f-measure 를 들이대면 안된다.
# 2. ROC curve & auc 
# 모델의 민감도(Sensitivity)와 특이도(Specifity) 의 관계를 표현한 그래프.
# X 축 : Sensitivity == TPR 
# Y 축 : 1 - Speicifity == FPR 
# TPR 과 FPR 은 반비례 관계 
pred <- prediction(result$predict, result$success)
roc.perf = performance(pred, measure = "tpr", x.measure = "fpr")
plot(roc.perf, ylab = "sensitivity ( TPR )", xlab = "1 - specificity ( FPR )")

# auc = Area Under the ROC Curve 
# auc 는 ROC Curve 의 아래면적이 크면 좋다는 것을 의미한다.
library(ROCR)
auc.perf = performance(pred, measure = "auc")
library(pROC)
auc.pROC = auc(result$success, result$predict)
paste('ROCR :', auc.perf@y.values , ' pROC : ', auc.pROC)
[1] "ROCR : 0.681419991398182  pROC :  0.681419991398182"
# extra visualization 
plot_pred_type_distribution <- function(df, threshold) {
  v <- rep(NA, nrow(df))
  v <- ifelse(df$prob >= threshold & df$success == 1, "TN", v)
  v <- ifelse(df$prob >= threshold & df$success == 0, "FN", v)
  v <- ifelse(df$prob < threshold  & df$success == 1, "FP", v)
  v <- ifelse(df$prob < threshold  & df$success == 0, "TP", v)
  
  df$predict <- v
  
  print(table(df$predict))
  
  ggplot(data=df, aes(x=success, y=prob)) + 
    geom_violin(fill=rgb(1,1,1,alpha=0.6), color=NA) + 
    geom_jitter(aes(color=predict), alpha=0.6) +
    geom_hline(yintercept=threshold, color="red", alpha=0.6) +
    scale_color_discrete(name = "type") +
    labs(title=sprintf("Threshold at %.2f", threshold))
}
plot_pred_type_distribution(result, 0.6)

   FN    FP    TN    TP 
13500 14320 36744 24344 

# 만약 서비스에서 success case 보다 fail case 를 더 잘 찾기를 원한다고 할때, 
# 기본적인 ROC curve 는 이를 잘 판단해주지 못한다.
# 이런 경우, 각각의 가중치를 두어 수치화해볼 수 도 있다.
# 물론 둘다 잘하면 좋다. 하지만 그렇지 못하는 경우... 하나만 더 잘 찾아내기를 원한다면.. 가중치를 두어 수치화해볼 수 있다.
calculate_roc <- function(df, cost_of_fp, cost_of_fn, n=100) {
  tpr <- function(df, threshold) {
    sum(df$prob <= threshold & df$success == 0) / sum(df$success == 0)
  }
  
  fpr <- function(df, threshold) {
    sum(df$prob <= threshold & df$success == 1) / sum(df$success == 1)
  }
  
  cost <- function(df, threshold, cost_of_fp, cost_of_fn) {
    sum(df$prob >= threshold & df$success == 0) * cost_of_fn + 
      sum(df$prob < threshold & df$success == 1) * cost_of_fp
  }
  
  roc <- data.frame(threshold = seq(0,1,length.out=n), tpr=NA, fpr=NA)
  roc$tpr <- sapply(roc$threshold, function(th) tpr(df, th))
  roc$fpr <- sapply(roc$threshold, function(th) fpr(df, th))
  roc$cost <- sapply(roc$threshold, function(th) cost(df, th, cost_of_fp, cost_of_fn))
  
  return(roc)
}
roc <- calculate_roc(result, 3, 1)
plot_roc <- function(roc, threshold, cost_of_fp, cost_of_fn) {
  library(gridExtra)
  
  norm_vec <- function(v) (v - min(v))/diff(range(v))
  
  idx_threshold = which.min(abs(roc$threshold-threshold))
  
  col_ramp <- colorRampPalette(c("green","orange","red","black"))(100)
  col_by_cost <- col_ramp[ceiling(norm_vec(roc$cost)*99)+1]
  p_roc <- ggplot(roc, aes(fpr,tpr)) + 
    geom_line(color=rgb(0,0,1,alpha=0.3)) +
    geom_point(color=col_by_cost, size=4, alpha=0.5) +
    coord_fixed() +
    geom_line(aes(threshold,threshold), color=rgb(0,0,1,alpha=0.5)) +
    labs(title = sprintf("ROC")) + xlab("FPR") + ylab("TPR") +
    geom_hline(yintercept=roc[idx_threshold,"tpr"], alpha=0.5, linetype="dashed") +
    geom_vline(xintercept=roc[idx_threshold,"fpr"], alpha=0.5, linetype="dashed")
  
  p_cost <- ggplot(roc, aes(threshold, cost)) +
    geom_line(color=rgb(0,0,1,alpha=0.3)) +
    geom_point(color=col_by_cost, size=4, alpha=0.5) +
    labs(title = sprintf("cost function")) +
    geom_vline(xintercept=threshold, alpha=0.5, linetype="dashed")
  
  sub_title <- sprintf("threshold at %.2f - cost of FP = %d, cost of FN = %d", threshold, cost_of_fp, cost_of_fn)
  grid.arrange(p_roc, p_cost, ncol=2)
}
# threshold = 0.83 / FP 가중치 : 3 , FN 가중치 : 1 
plot_roc(roc, 0.83, 3, 1)

# 3. cross validation
# 아래의 그림처럼 특정 data set 을 n 개 의 bucket 으로 나누고, n 회 반복하여 train set 과 test set 을 변경하여 모델을 평가한다. 
# 이를 통해 cherry-picked 되는 케이스를 걸러낼 수 있다. 
# 3.1 data partition
success_dataset   <- filter(raw, success == 1)
train_set_success <- sample_frac(success_dataset, 0.2)
test_set_success  <- setdiff(success_dataset, train_set_success)
# train_set <- rbind(train_set_success, train_set_fail)
paste("total : ", nrow(success_dataset), " train : " , nrow(train_set_success), " test : ", nrow(test_set_success))
[1] "total :  80315  train :  16063  test :  64252"
# 3.2 bucket
library(caret)
folds <- createFolds(raw$success, k = 10)
str(folds)
List of 10
 $ Fold01: int [1:13019] 3 6 12 15 20 23 31 73 74 78 ...
 $ Fold02: int [1:13020] 9 18 22 47 59 68 76 111 113 154 ...
 $ Fold03: int [1:13020] 2 30 41 49 62 71 72 84 101 102 ...
 $ Fold04: int [1:13020] 28 34 36 37 45 46 48 51 52 58 ...
 $ Fold05: int [1:13020] 10 13 27 56 97 108 117 146 149 151 ...
 $ Fold06: int [1:13020] 17 24 40 50 54 55 61 63 65 70 ...
 $ Fold07: int [1:13020] 1 7 14 33 53 57 81 83 87 90 ...
 $ Fold08: int [1:13020] 11 19 42 43 44 66 69 82 106 107 ...
 $ Fold09: int [1:13019] 4 8 16 21 25 29 38 60 89 98 ...
 $ Fold10: int [1:13020] 5 26 32 35 39 64 77 88 91 96 ...
test <- raw[folds$Fold01, ]
table(raw$success)

    0     1 
49883 80315 
table(test$success)

   0    1 
4970 8049 
# 4. kappa stat
# Kappa Statistic compares the accuracy of the system to the accuracy of a random system
# 따라서, 이 값이 작을 수록 좋은 놈이다.
# 예를들어 정답인 놈들만을 가지고 kappa 를 구해보면, 아래와 같이 1 에 가까운 값이 된다. 
tp <- head(subset(result, success == 0 & predict == 0), 10000)
r <- rbind(tp, head(subset(result, success == 0 & predict == 1), 1))
r <- rbind(r, head(subset(result, success == 1 & predict == 0), 1))
r <- rbind(r, head(subset(result, success == 1 & predict == 1), 10000))
cm <- confusionMatrix(r$predict, r$success)
print(cm$overall)
      Accuracy          Kappa  AccuracyLower  AccuracyUpper   AccuracyNull AccuracyPValue  McnemarPValue 
     0.9999000      0.9998000      0.9996388      0.9999879      0.5000000      0.0000000      1.0000000 
# 그리고 틀린 놈들의 비중을 높여서 kappa 를 보면, -1 에 가까운 값을 갖는다.
tp <- head(subset(result, success == 0 & predict == 0), 10)
r2 <- rbind(tp, head(subset(result, success == 0 & predict == 1), 1000))
r2 <- rbind(r2, head(subset(result, success == 1 & predict == 0), 1000))
r2 <- rbind(r2, head(subset(result, success == 1 & predict == 1), 10))
cm <- confusionMatrix(r2$predict, r2$success)
print(cm$overall)
      Accuracy          Kappa  AccuracyLower  AccuracyUpper   AccuracyNull AccuracyPValue  McnemarPValue 
   0.009900990   -0.980198020    0.006057974    0.015250042    0.500000000    1.000000000    1.000000000 
# Kappa 통계량은 아래와 같은 기준을 가지고 생각하면 되고, 산식은 아래와 같다.
# Kappa Agreement
# < 0 Less than chance agreement
# 0.01–0.20 Slight agreement
# 0.21–0.40 Fair agreement
# 0.41–0.60 Moderate agreement
# 0.61–0.80 Substantial agreement
# 0.81–0.99 Almost perfect agreement
# 그러면 왜 kappa 를 보는가?
# 예를 들어, 대부분 실패하는 실제 상황에 대해서, 우연하게도 대부분 실패할 것이라고 예측하는 모델이 있다면, 
# Accuracy 값은 매우 높지만, kappa 값은 매우 낮게 나오게 됨을 알 수 있다. 
# kappa 는 매우 한쪽으로 skew 되어 있는 categorical var 에 대해 예측을 할 때, 유의깊게 살펴봐야 한다.  
st <- head(subset(result, success == 0 & predict == 0), 10000)
r3<- rbind(st, head(subset(result, success == 0 & predict == 1), 100))
r3 <- rbind(r3, head(subset(result, success == 1 & predict == 0), 100))
r3 <- rbind(r3, head(subset(result, success == 1 & predict == 1), 20))
cm <- confusionMatrix(r3$predict, r3$success)
print(cm$overall)
      Accuracy          Kappa  AccuracyLower  AccuracyUpper   AccuracyNull AccuracyPValue  McnemarPValue 
     0.9804305      0.1567657      0.9775551      0.9830273      0.9882583      1.0000000      1.0000000 
# 5. 적합한 measurement 는 어떤 것인가? 케이스 분석 
# 5.1 매우 조심스럽게 fail 케이스를 탐지하고, fail 이 예상되는 경우 보수적인 대책을 제시하는 것이 목표라면 
# precision of fail 이 제일 중요한 요소가 된다.  ( threshold = 0.1 선택 )
# 5.3 매우 공격적으로 fail 케이스를 탐지하고, FN 이 발생할 경우 risk 를 감당해낼 수 있다면,
# recall of fail 이 제일 중요한 요소가 된다. ( threshold > 0.7 선택 )
# 5.2 길 찾기 표지판에서 오른쪽 왼쪽을 맞추는 문제를 푸는 것이라면, 
# accuracy 혹은 f-measure 가 기준이 된다.
#ref : http://www.circulation.or.kr/workshop/2016spring/file/%EB%8C%80%ED%95%9C%EC%8B%AC%EC%9E%A5%ED%95%99%ED%9A%8C%20%EC%B6%98%EA%B3%84%EC%9B%90%EA%B3%A0/ksc226.pdf
# 6. 정리 
# EDA 와 기본적인 cleaning 에 필요한 통계적 고찰과 
# 모델의 결과에 대한 measurement 방식과 선택에 대한 판단이 갖춰지면, 
# 적합한 기법을 찾아 적용하면 된다. 
# 모델을 튜닝하고 앙상블하는 과정도 중요하지만, 가장 중요한 것 세가지는 cleaning 과 feature eng. 그리고 적절한 판단법에 근거한 의사결정이다.
LS0tCnRpdGxlOiAiTW9kZWwgRXZhbHVhdGlvbiAmIFJPQyBjdXJ2ZSIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKYGBge3J9CiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCiMgTW9kZWwgRXZhbHVhdGlvbiAmIFJPQyBjdXJ2ZSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjCiMgcmVmIDogbWFjaGluZSBsZWFybmluZyB3aXRoIFIsIENIIDEwICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjCiMgcmVmIDogaHR0cHM6Ly93d3cuci1ibG9nZ2Vycy5jb20vYS1zbWFsbC1pbnRyb2R1Y3Rpb24tdG8tdGhlLXJvY3ItcGFja2FnZS8gICAjCiMgcmVmIDogaHR0cHM6Ly93d3cuci1ibG9nZ2Vycy5jb20vaWxsdXN0cmF0ZWQtZ3VpZGUtdG8tcm9jLWFuZC1hdWMvICAgICAgICAgICAjCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCgojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwojIHRlcm1zICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIwojIFRQIEZOIFRGIEZQICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIwojIHJlY2FsbCAsIHByZWNpc29uICwgYWNjdXJhY3kgLCBlcnJvciByYXRlICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIwojIFNlbnNpdGl2aXR5ICwgU3BlY2lmaXR5ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIwojIEthcHBhIFN0YXQgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIwojIEYgbWVhc3VyZSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIwojIHJvYyBjdXJ2ZSAsIGF1YyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyAgCiMgY3Jvc3MgdmFsaWRhdGlvbiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCgojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwojIHBhY2thZ2UgJiBtZXRob2RzICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIwojIENyb3NzVGFibGUgaW4gZ21vZGVscyBwYWNrYWdlICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyAKIyBjb25mdXNpb25NYXRyaXggaW4gY2FyZXQgcGFja2FnZSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMKIyBjcmVhdGVGb2xkcyBpbiBjYXJldCBwYWNrYWdlICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMKIyBST0NSIHBhY2thZ2UgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMKIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMKYGBgCgohW10oL1VzZXJzL0NBL0Rvd25sb2Fkcy9iYXNpY190ZXJtLnBuZykKCmBgYHtyfQojMC4g6riw67O47KCB7J24IG1vZGVsIGV2YWx1YXRpb24g7JeQIOyTsOydtOuKlCDsp4DtkZzrk6TsnYAg7JyE7JmAIOqwmeuLpC4KIyDshJzruYTsiqTsl5DshJwg7YOQ7KeA7ZWY66Ck64qUIOqyg+ydtCDslrTrlqQg6rKD7J246rCA7JeQIOuUsOudvCwg66qo64247J2YIOyEseuKpeydhCDtj4nqsIDtlZjripQg7LKZ64+E64+EIOuLrOudvOyngOq4sCDrp4jroKjsnbjrjbAsIAojIOq4sOuzuOyggeycvOuhnCBjb25mdXNpb24gbWF0cml4IOydmCDrhKTqsIDsp4Ag6rCS7J2YIOyhsO2VqeycvOuhnCDrp4zrk6TslrTsp4Tri6QuCmBgYAoKCmBgYHtyfQojMS4gcHJlZGljdGlvbiDqsrDqs7wgRGF0YSBGcmFtZSAKIyBzdWNjZXNzIDog7Iuk7KCcIOyEseqztSDsl6zrtoAg6rCSIAojIHByb2IgICAgOiDshLHqs7XtlaDtmZXrpaAg7JiI7Lih6rCSCiMgcHJlZGljdCA6IHRocmVzaG9sZCAwLjYg7J2EIOq4sOykgOycvOuhnCwgdGhyZXNob2xkIOqwkuuztOuLpCDtgazrqbQg7ISx6rO17J2065286rOgIO2MkOuLqO2VnCDstZzsooUg7JiI7Lih6rCSIApoZWFkKHJlc3VsdCkKYGBgCgoKYGBge3IsIGVjaG8gPSBUfQojMS4xIOq4sOy0iOyggeyduCBBY2N1cmFjeSAsIFByZWNpc2lvbiwgUmVjYWxsIOydhCDqtaztlbTrs7TsnpAgKCArIFNlbnNpdGl2aXR5ICwgU3BlY2lmaWNpdHkgKQoKZXZhbHVhdGVfbW9kZWwgPC0gZnVuY3Rpb24oZGYpIHsKICBhIDwtIGZpbHRlcihkZiwgcHJlZGljdCA9PSAxICYgc3VjY2VzcyA9PSAxKQogIGIgPC0gZmlsdGVyKGRmLCBwcmVkaWN0ID09IDAgJiBzdWNjZXNzID09IDEpCiAgYyA8LSBmaWx0ZXIoZGYsIHByZWRpY3QgPT0gMCAmIHN1Y2Nlc3MgPT0gMCkKICBkIDwtIGZpbHRlcihkZiwgcHJlZGljdCA9PSAxICYgc3VjY2VzcyA9PSAwKQogIAogIHN1Y2Nlc3NfcHJlY2lzaW9uIDwtIG5yb3coYSkgLyAobnJvdyhhKSArIG5yb3coZCkpIAogIHN1Y2Nlc3NfcmVjYWxsICAgIDwtIG5yb3coYSkgLyAobnJvdyhhKSArIG5yb3coYikpIAogIGZhaWxfcHJlY2lzaW9uICAgIDwtIG5yb3coYykgLyAobnJvdyhiKSArIG5yb3coYykpIAogIGZhaWxfcmVjYWxsICAgICAgIDwtIG5yb3coYykgLyAobnJvdyhjKSArIG5yb3coZCkpICAKICBhY2N1cmFjeSAgICAgICAgICA8LSAobnJvdyhhKSArIG5yb3coYykpIC8gbnJvdyhkZikKICAKICBldmFsdWF0aW9uX3Jlc3VsdCA8LSBhcy5kYXRhLmZyYW1lKGxpc3QoCiAgICBgc3VjY2Vzc19wcmVjaXNpb25gID0gc3VjY2Vzc19wcmVjaXNpb24sIAogICAgYHN1Y2Nlc3NfcmVjYWxsYCA9IHN1Y2Nlc3NfcmVjYWxsLCAKICAgIGBmYWlsX3ByZWNpc2lvbmAgPSBmYWlsX3ByZWNpc2lvbiwgIAogICAgYGZhaWxfcmVjYWxsYCA9IGZhaWxfcmVjYWxsLCAKICAgIGBhY2N1cmFjeWAgPSBhY2N1cmFjeQogICkpCiAgCiAgcmV0dXJuKGV2YWx1YXRpb25fcmVzdWx0KQp9CgoKcHJpbnQoZXZhbHVhdGVfbW9kZWwocmVzdWx0KSkKYGBgCgoKYGBge3J9CiMgcHJlY2lzaW9uIOqzvCByZWNhbGwg7JWe7JeQIHN1Y2Nlc3MgLyBmYWlsIOydtOudvOuKlCBwcmVmaXgg6rCAIOyeiOuLpC4gCiMg7JiI7Lih66qo64247JeQ7IScIOyjvOyViOygkOydhCDrkazshJwsIO2DkOyngO2VtCDrgrTslbztlaAg64yA7IOB7J20IHN1Y2Nlc3Mg7J2064OQIGZhaWwg7J2064OQ7JeQIOuUsOudvOyEnCDri6zrnbzsp4gg7IiYIOyeiOuLpOuKlCDsnbTslbzquLDsnbjrjbAsIAojIOychOydmCBjb25mdXNpb24gbWF0cml4IOydmCDquLDspIDsnbQgQWN0dWFsbHkgU3BhbSDsnbTrg5AgQWN1dGFsbHkgSGFtIOydtOuDkOydmCDssKjsnbTsnbTri6QuIAoKIzEuMiAg7KeB7KCRIOq1rO2YhOydhCDtlbTshJwg6riw7LSIIO2PieqwgCDsp4DtkZzrpbwg672R7JWY7Jy864KYLCDrnbzsnbTruIzrn6zrpqzrpbwg7IKs7Jqp7ZW064+EIOuQnOuLpC4KYGBgCgoKYGBge3J9CmxpYnJhcnkoZ21vZGVscykKQ3Jvc3NUYWJsZShyZXN1bHQkc3VjY2VzcywgcmVzdWx0JHByZWRpY3QpCmBgYAoKYGBge3J9CmxpYnJhcnkoY2FyZXQpCmNvbmZ1c2lvbk1hdHJpeChyZXN1bHQkcHJlZGljdCwgcmVzdWx0JHN1Y2Nlc3MpCgojIHNlbnNpdGl2aXR5ID09IGZhaWwgcmVjYWxsICgg7KeE7KecIGZhaWwg7KSR7JeQIGZhaWwg7J2EIOyWvOuniOuCmCBwcmVkaWN0aW9uIO2WiOuKlOqwgCApID09IFBvc3RpdmllIENsYXNzIOykkSDrqofqsJzrpbwgUG9zaXRpdmUg65286rOgIO2WiOuKlOqwgCA9PSBUUFIKIyBzcGVjaWZpY2l0eSA9PSBzdWNjZXNzIHJlY2FsbCAoIOynhOynnCBzdWNjZXNzIOykkeyXkCBzdWNjZXNzIOulvCDslrzrp4jrgpggcHJlZGljdGlvbiDtlojripTqsIAgKSA9PSBOZWdhdGl2ZSBDbGFzcyDspJEg66qH6rCc66W8IE5lZ2F0aXZlIOudvOqzoCDtlojripTqsIAgPT0gMSAtIEZQUgpgYGAKCgpgYGB7cn0KIyAxLjMg6rCc67OE7KCB7J24IOyngO2RnOuTpOydgCDsnbTsoJwg7IK07Y6067Sk64ukLiAKIyDqt7jrn6zri4jquYwsIHByZWNpc2lvbiAvIHJlY2FsbCAvIHNlbnNpdGl2aXR5IC8gc3BlY2lmaWNpdHkg7JmAIFByZWNpc2lvbiDqs7wgUmVjYWxsIOydmCDsgrDsiKDtj4nqt6An7Iqk65+s7Jq0JyBBY2N1cmFjeSDquYzsp4AKIyDslYTsp4Eg7JWIIOuzuCDqsoPsnbQgRi1tZWFzdXJlIOyduOuNsCwg7JyE7J2YIOyLneydhCDrs7TrqbQg7KGw7ZmUIO2Pieq3oChoYXJtb25pYyBtZWFuKSDsnYQg7IKs7Jqp7ZWY6rOgIOyeiOuLpC4gCgojIEYtbWVhc3VyZSDripQg6rCB6rCBIO2RnO2YhOuQmOuKlCDrkZDqsJzsnZgg6rCSIHByZWNpc2lvbiDqs7wgcmVjYWxsIOydhCBjb21iaW5lIO2VmOyXrCDrgpjtg4DrgrTquLAg7JyE7ZWcIOqyg+ydtOuLpC4KIyDsgrDsi53snYAg6rCE64uo7ZWY6rOgLCDrhpLsnLzrqbQg64yA7LK07KCB7Jy866GcIHByZWNpc2lvbiDqs7wgcmVjYWxsIOydtCDrqqjrkZAg7Jqw7IiY7ZWY64uk64qUIOqyg+ydhCDrp5DtlZzri6QuCgojIO2VmOyngOunjCDsmZw/IOyCsOyIoCDtj4nqt6Ag66eQ6rOgIOyhsO2ZlCDtj4nqt6DsnbjqsIA/CiMgcmVmIDogaHR0cDovL3d3dy40Zm91ci51cy9hcnRpY2xlLzIwMTMvMDkvaG93LXRvLWNvbWJpbmUtdHdvLXZhbHVlcwpgYGAKCiFbXSgvVXNlcnMvQ0EvRG93bmxvYWRzL21lYW4ucG5nKQoKCmBgYHtyfQojIOychOydmCDqt7jrprzqs7wg66eB7YGs7JeQ7IScIOyEpOuqheuQmOuTr+ydtCwgCiMgcHJlY2lzaW9uICwgcmVjYWxsIOykkSDtlZzsqr3snbQg7KeA64KY7LmY6rKMIOuCmOyBnCDqsr3smrAgCiMgZXg+IOyLpOygnCDrjbDsnbTthLDsnZgg7Iuk7YyoOuyEseqztSA9IDAuOTk6MC4wMSDsnbgg6rK97JqwLCDshLHqs7XsnYQg7JiI7Lih7ZWY64qUIOqyveyasCByZWNhbGwg7J2AIOq1ieyepe2eiCDsoovsnYAg67CY66m0IHByZWNpc2lvbiDsnbQg7JeJ66ed7J28IOyImCDsnojri6QuCiMg7J20IOqyveyasCwgYWNjdXJhY3kg66W8IO2Gte2VtCDtj4nqsIDrpbwg7ZWY66m0IOuPhOuTnOudvOyngOyngCDslYrsp4Drp4wsIGYtbWVhc3VyZSDrpbwg7ZWY66m0IOqwkuydtCDsnbzsoJUg7IiY7KSAIOydtOyDgSDsmKzrnbzqsIgg7IiY6rCAIOyXhuuLpC4KIyDso7zsnZggOiDrqqjrk6Ag6rK97Jqw7JeQIGFjY3VyYWN5IC8gZi1tZWFzdXJlIOulvCDrk6TsnbTrjIDrqbQg7JWI65Cc64ukLgpgYGAKCgpgYGB7cn0KIyAyLiBST0MgY3VydmUgJiBhdWMgCiMg66qo64247J2YIOuvvOqwkOuPhChTZW5zaXRpdml0eSnsmYAg7Yq57J2064+EKFNwZWNpZml0eSkg7J2YIOq0gOqzhOulvCDtkZztmITtlZwg6re4656Y7ZSELgojIFgg7LaVIDogU2Vuc2l0aXZpdHkgPT0gVFBSIAojIFkg7LaVIDogMSAtIFNwZWljaWZpdHkgPT0gRlBSIAoKcHJlZCA8LSBwcmVkaWN0aW9uKHJlc3VsdCRwcmVkaWN0LCByZXN1bHQkc3VjY2VzcykKcm9jLnBlcmYgPSBwZXJmb3JtYW5jZShwcmVkLCBtZWFzdXJlID0gInRwciIsIHgubWVhc3VyZSA9ICJmcHIiKQpwbG90KHJvYy5wZXJmLCB5bGFiID0gInNlbnNpdGl2aXR5ICggVFBSICkiLCB4bGFiID0gIjEgLSBzcGVjaWZpY2l0eSAoIEZQUiApIikKYGBgCgoKYGBge3J9CiMgYXVjID0gQXJlYSBVbmRlciB0aGUgUk9DIEN1cnZlIAojIGF1YyDripQgUk9DIEN1cnZlIOydmCDslYTrnpjrqbTsoIHsnbQg7YGs66m0IOyii+uLpOuKlCDqsoPsnYQg7J2Y66+47ZWc64ukLgpsaWJyYXJ5KFJPQ1IpCmF1Yy5wZXJmID0gcGVyZm9ybWFuY2UocHJlZCwgbWVhc3VyZSA9ICJhdWMiKQoKbGlicmFyeShwUk9DKQphdWMucFJPQyA9IGF1YyhyZXN1bHQkc3VjY2VzcywgcmVzdWx0JHByZWRpY3QpCgpwYXN0ZSgnUk9DUiA6JywgYXVjLnBlcmZAeS52YWx1ZXMgLCAnIHBST0MgOiAnLCBhdWMucFJPQykKCmBgYAoKYGBge3J9CiMgZXh0cmEgdmlzdWFsaXphdGlvbiAKcGxvdF9wcmVkX3R5cGVfZGlzdHJpYnV0aW9uIDwtIGZ1bmN0aW9uKGRmLCB0aHJlc2hvbGQpIHsKICB2IDwtIHJlcChOQSwgbnJvdyhkZikpCiAgdiA8LSBpZmVsc2UoZGYkcHJvYiA+PSB0aHJlc2hvbGQgJiBkZiRzdWNjZXNzID09IDEsICJUTiIsIHYpCiAgdiA8LSBpZmVsc2UoZGYkcHJvYiA+PSB0aHJlc2hvbGQgJiBkZiRzdWNjZXNzID09IDAsICJGTiIsIHYpCiAgdiA8LSBpZmVsc2UoZGYkcHJvYiA8IHRocmVzaG9sZCAgJiBkZiRzdWNjZXNzID09IDEsICJGUCIsIHYpCiAgdiA8LSBpZmVsc2UoZGYkcHJvYiA8IHRocmVzaG9sZCAgJiBkZiRzdWNjZXNzID09IDAsICJUUCIsIHYpCiAgCiAgZGYkcHJlZGljdCA8LSB2CiAgCiAgcHJpbnQodGFibGUoZGYkcHJlZGljdCkpCiAgCiAgZ2dwbG90KGRhdGE9ZGYsIGFlcyh4PXN1Y2Nlc3MsIHk9cHJvYikpICsgCiAgICBnZW9tX3Zpb2xpbihmaWxsPXJnYigxLDEsMSxhbHBoYT0wLjYpLCBjb2xvcj1OQSkgKyAKICAgIGdlb21faml0dGVyKGFlcyhjb2xvcj1wcmVkaWN0KSwgYWxwaGE9MC42KSArCiAgICBnZW9tX2hsaW5lKHlpbnRlcmNlcHQ9dGhyZXNob2xkLCBjb2xvcj0icmVkIiwgYWxwaGE9MC42KSArCiAgICBzY2FsZV9jb2xvcl9kaXNjcmV0ZShuYW1lID0gInR5cGUiKSArCiAgICBsYWJzKHRpdGxlPXNwcmludGYoIlRocmVzaG9sZCBhdCAlLjJmIiwgdGhyZXNob2xkKSkKfQoKcGxvdF9wcmVkX3R5cGVfZGlzdHJpYnV0aW9uKHJlc3VsdCwgMC42KQpgYGAKCgpgYGB7cn0KIyDrp4zslb0g7ISc67mE7Iqk7JeQ7IScIHN1Y2Nlc3MgY2FzZSDrs7Tri6QgZmFpbCBjYXNlIOulvCDrjZQg7J6YIOywvuq4sOulvCDsm5DtlZzri6Tqs6Ag7ZWg65WMLCAKIyDquLDrs7jsoIHsnbggUk9DIGN1cnZlIOuKlCDsnbTrpbwg7J6YIO2MkOuLqO2VtOyjvOyngCDrqrvtlZzri6QuCiMg7J2065+wIOqyveyasCwg6rCB6rCB7J2YIOqwgOykkey5mOulvCDrkZDslrQg7IiY7LmY7ZmU7ZW067O8IOyImCDrj4Qg7J6I64ukLgojIOusvOuhoCDrkZjri6Qg7J6Y7ZWY66m0IOyii+uLpC4g7ZWY7KeA66eMIOq3uOugh+yngCDrqrvtlZjripQg6rK97JqwLi4uIO2VmOuCmOunjCDrjZQg7J6YIOywvuyVhOuCtOq4sOulvCDsm5DtlZzri6TrqbQuLiDqsIDspJHsuZjrpbwg65GQ7Ja0IOyImOy5mO2ZlO2VtOuzvCDsiJgg7J6I64ukLgoKY2FsY3VsYXRlX3JvYyA8LSBmdW5jdGlvbihkZiwgY29zdF9vZl9mcCwgY29zdF9vZl9mbiwgbj0xMDApIHsKICB0cHIgPC0gZnVuY3Rpb24oZGYsIHRocmVzaG9sZCkgewogICAgc3VtKGRmJHByb2IgPD0gdGhyZXNob2xkICYgZGYkc3VjY2VzcyA9PSAwKSAvIHN1bShkZiRzdWNjZXNzID09IDApCiAgfQogIAogIGZwciA8LSBmdW5jdGlvbihkZiwgdGhyZXNob2xkKSB7CiAgICBzdW0oZGYkcHJvYiA8PSB0aHJlc2hvbGQgJiBkZiRzdWNjZXNzID09IDEpIC8gc3VtKGRmJHN1Y2Nlc3MgPT0gMSkKICB9CiAgCiAgY29zdCA8LSBmdW5jdGlvbihkZiwgdGhyZXNob2xkLCBjb3N0X29mX2ZwLCBjb3N0X29mX2ZuKSB7CiAgICBzdW0oZGYkcHJvYiA+PSB0aHJlc2hvbGQgJiBkZiRzdWNjZXNzID09IDApICogY29zdF9vZl9mbiArIAogICAgICBzdW0oZGYkcHJvYiA8IHRocmVzaG9sZCAmIGRmJHN1Y2Nlc3MgPT0gMSkgKiBjb3N0X29mX2ZwCiAgfQogIAogIHJvYyA8LSBkYXRhLmZyYW1lKHRocmVzaG9sZCA9IHNlcSgwLDEsbGVuZ3RoLm91dD1uKSwgdHByPU5BLCBmcHI9TkEpCiAgcm9jJHRwciA8LSBzYXBwbHkocm9jJHRocmVzaG9sZCwgZnVuY3Rpb24odGgpIHRwcihkZiwgdGgpKQogIHJvYyRmcHIgPC0gc2FwcGx5KHJvYyR0aHJlc2hvbGQsIGZ1bmN0aW9uKHRoKSBmcHIoZGYsIHRoKSkKICByb2MkY29zdCA8LSBzYXBwbHkocm9jJHRocmVzaG9sZCwgZnVuY3Rpb24odGgpIGNvc3QoZGYsIHRoLCBjb3N0X29mX2ZwLCBjb3N0X29mX2ZuKSkKICAKICByZXR1cm4ocm9jKQp9Cgpyb2MgPC0gY2FsY3VsYXRlX3JvYyhyZXN1bHQsIDMsIDEpCmBgYAoKYGBge3J9CnBsb3Rfcm9jIDwtIGZ1bmN0aW9uKHJvYywgdGhyZXNob2xkLCBjb3N0X29mX2ZwLCBjb3N0X29mX2ZuKSB7CiAgbGlicmFyeShncmlkRXh0cmEpCiAgCiAgbm9ybV92ZWMgPC0gZnVuY3Rpb24odikgKHYgLSBtaW4odikpL2RpZmYocmFuZ2UodikpCiAgCiAgaWR4X3RocmVzaG9sZCA9IHdoaWNoLm1pbihhYnMocm9jJHRocmVzaG9sZC10aHJlc2hvbGQpKQogIAogIGNvbF9yYW1wIDwtIGNvbG9yUmFtcFBhbGV0dGUoYygiZ3JlZW4iLCJvcmFuZ2UiLCJyZWQiLCJibGFjayIpKSgxMDApCiAgY29sX2J5X2Nvc3QgPC0gY29sX3JhbXBbY2VpbGluZyhub3JtX3ZlYyhyb2MkY29zdCkqOTkpKzFdCiAgcF9yb2MgPC0gZ2dwbG90KHJvYywgYWVzKGZwcix0cHIpKSArIAogICAgZ2VvbV9saW5lKGNvbG9yPXJnYigwLDAsMSxhbHBoYT0wLjMpKSArCiAgICBnZW9tX3BvaW50KGNvbG9yPWNvbF9ieV9jb3N0LCBzaXplPTQsIGFscGhhPTAuNSkgKwogICAgY29vcmRfZml4ZWQoKSArCiAgICBnZW9tX2xpbmUoYWVzKHRocmVzaG9sZCx0aHJlc2hvbGQpLCBjb2xvcj1yZ2IoMCwwLDEsYWxwaGE9MC41KSkgKwogICAgbGFicyh0aXRsZSA9IHNwcmludGYoIlJPQyIpKSArIHhsYWIoIkZQUiIpICsgeWxhYigiVFBSIikgKwogICAgZ2VvbV9obGluZSh5aW50ZXJjZXB0PXJvY1tpZHhfdGhyZXNob2xkLCJ0cHIiXSwgYWxwaGE9MC41LCBsaW5ldHlwZT0iZGFzaGVkIikgKwogICAgZ2VvbV92bGluZSh4aW50ZXJjZXB0PXJvY1tpZHhfdGhyZXNob2xkLCJmcHIiXSwgYWxwaGE9MC41LCBsaW5ldHlwZT0iZGFzaGVkIikKICAKICBwX2Nvc3QgPC0gZ2dwbG90KHJvYywgYWVzKHRocmVzaG9sZCwgY29zdCkpICsKICAgIGdlb21fbGluZShjb2xvcj1yZ2IoMCwwLDEsYWxwaGE9MC4zKSkgKwogICAgZ2VvbV9wb2ludChjb2xvcj1jb2xfYnlfY29zdCwgc2l6ZT00LCBhbHBoYT0wLjUpICsKICAgIGxhYnModGl0bGUgPSBzcHJpbnRmKCJjb3N0IGZ1bmN0aW9uIikpICsKICAgIGdlb21fdmxpbmUoeGludGVyY2VwdD10aHJlc2hvbGQsIGFscGhhPTAuNSwgbGluZXR5cGU9ImRhc2hlZCIpCiAgCiAgc3ViX3RpdGxlIDwtIHNwcmludGYoInRocmVzaG9sZCBhdCAlLjJmIC0gY29zdCBvZiBGUCA9ICVkLCBjb3N0IG9mIEZOID0gJWQiLCB0aHJlc2hvbGQsIGNvc3Rfb2ZfZnAsIGNvc3Rfb2ZfZm4pCgogIGdyaWQuYXJyYW5nZShwX3JvYywgcF9jb3N0LCBuY29sPTIpCn0KCiMgdGhyZXNob2xkID0gMC44MyAvIEZQIOqwgOykkey5mCA6IDMgLCBGTiDqsIDspJHsuZggOiAxIApwbG90X3JvYyhyb2MsIDAuODMsIDMsIDEpCmBgYAoKYGBge3J9CiMgMy4gY3Jvc3MgdmFsaWRhdGlvbgojIOyVhOuemOydmCDqt7jrprzsspjrn7wg7Yq57KCVIGRhdGEgc2V0IOydhCBuIOqwnCDsnZggYnVja2V0IOycvOuhnCDrgpjriITqs6AsIG4g7ZqMIOuwmOuzte2VmOyXrCB0cmFpbiBzZXQg6rO8IHRlc3Qgc2V0IOydhCDrs4Dqsr3tlZjsl6wg66qo64247J2EIO2PieqwgO2VnOuLpC4gCiMg7J2066W8IO2Gte2VtCBjaGVycnktcGlja2VkIOuQmOuKlCDsvIDsnbTsiqTrpbwg6rG465+s64K8IOyImCDsnojri6QuIApgYGAKCiFbXSgvVXNlcnMvQ0EvRG93bmxvYWRzL3ZhbGlkYXRpb25fZGF0YXNldC5wbmcpCgohW10oL1VzZXJzL0NBL0Rvd25sb2Fkcy9jcm9zc192YWxpZGF0aW9uLnBuZykKCmBgYHtyfQojIDMuMSBkYXRhIHBhcnRpdGlvbgpzdWNjZXNzX2RhdGFzZXQgICA8LSBmaWx0ZXIocmF3LCBzdWNjZXNzID09IDEpCnRyYWluX3NldF9zdWNjZXNzIDwtIHNhbXBsZV9mcmFjKHN1Y2Nlc3NfZGF0YXNldCwgMC4yKQp0ZXN0X3NldF9zdWNjZXNzICA8LSBzZXRkaWZmKHN1Y2Nlc3NfZGF0YXNldCwgdHJhaW5fc2V0X3N1Y2Nlc3MpCiMgdHJhaW5fc2V0IDwtIHJiaW5kKHRyYWluX3NldF9zdWNjZXNzLCB0cmFpbl9zZXRfZmFpbCkKCnBhc3RlKCJ0b3RhbCA6ICIsIG5yb3coc3VjY2Vzc19kYXRhc2V0KSwgIiB0cmFpbiA6ICIgLCBucm93KHRyYWluX3NldF9zdWNjZXNzKSwgIiB0ZXN0IDogIiwgbnJvdyh0ZXN0X3NldF9zdWNjZXNzKSkKYGBgCgpgYGB7cn0KIyAzLjIgYnVja2V0CmxpYnJhcnkoY2FyZXQpCmZvbGRzIDwtIGNyZWF0ZUZvbGRzKHJhdyRzdWNjZXNzLCBrID0gMTApCnN0cihmb2xkcykKCnRlc3QgPC0gcmF3W2ZvbGRzJEZvbGQwMSwgXQoKdGFibGUocmF3JHN1Y2Nlc3MpCnRhYmxlKHRlc3Qkc3VjY2VzcykKYGBgCgpgYGB7cn0KIyA0LiBrYXBwYSBzdGF0CiMgS2FwcGEgU3RhdGlzdGljIGNvbXBhcmVzIHRoZSBhY2N1cmFjeSBvZiB0aGUgc3lzdGVtIHRvIHRoZSBhY2N1cmFjeSBvZiBhIHJhbmRvbSBzeXN0ZW0KIyDrlLDrnbzshJwsIOydtCDqsJLsnbQg7J6R7J2EIOyImOuhnSDsoovsnYAg64aI7J2064ukLgojIOyYiOulvOuTpOyWtCDsoJXri7Xsnbgg64aI65Ok66eM7J2EIOqwgOyngOqzoCBrYXBwYSDrpbwg6rWs7ZW067O066m0LCDslYTrnpjsmYAg6rCZ7J20IDEg7JeQIOqwgOq5jOyatCDqsJLsnbQg65Cc64ukLiAKCnRwIDwtIGhlYWQoc3Vic2V0KHJlc3VsdCwgc3VjY2VzcyA9PSAwICYgcHJlZGljdCA9PSAwKSwgMTAwMDApCnIgPC0gcmJpbmQodHAsIGhlYWQoc3Vic2V0KHJlc3VsdCwgc3VjY2VzcyA9PSAwICYgcHJlZGljdCA9PSAxKSwgMSkpCnIgPC0gcmJpbmQociwgaGVhZChzdWJzZXQocmVzdWx0LCBzdWNjZXNzID09IDEgJiBwcmVkaWN0ID09IDApLCAxKSkKciA8LSByYmluZChyLCBoZWFkKHN1YnNldChyZXN1bHQsIHN1Y2Nlc3MgPT0gMSAmIHByZWRpY3QgPT0gMSksIDEwMDAwKSkKCmNtIDwtIGNvbmZ1c2lvbk1hdHJpeChyJHByZWRpY3QsIHIkc3VjY2VzcykKcHJpbnQoY20kb3ZlcmFsbCkKYGBgCgpgYGB7cn0KIyDqt7jrpqzqs6Ag7YuA66awIOuGiOuTpOydmCDruYTspJHsnYQg64aS7Jes7IScIGthcHBhIOulvCDrs7TrqbQsIC0xIOyXkCDqsIDquYzsmrQg6rCS7J2EIOqwluuKlOuLpC4KdHAgPC0gaGVhZChzdWJzZXQocmVzdWx0LCBzdWNjZXNzID09IDAgJiBwcmVkaWN0ID09IDApLCAxMCkKcjIgPC0gcmJpbmQodHAsIGhlYWQoc3Vic2V0KHJlc3VsdCwgc3VjY2VzcyA9PSAwICYgcHJlZGljdCA9PSAxKSwgMTAwMCkpCnIyIDwtIHJiaW5kKHIyLCBoZWFkKHN1YnNldChyZXN1bHQsIHN1Y2Nlc3MgPT0gMSAmIHByZWRpY3QgPT0gMCksIDEwMDApKQpyMiA8LSByYmluZChyMiwgaGVhZChzdWJzZXQocmVzdWx0LCBzdWNjZXNzID09IDEgJiBwcmVkaWN0ID09IDEpLCAxMCkpCgpjbSA8LSBjb25mdXNpb25NYXRyaXgocjIkcHJlZGljdCwgcjIkc3VjY2VzcykKcHJpbnQoY20kb3ZlcmFsbCkKYGBgCgpgYGB7cn0KIyBLYXBwYSDthrXqs4Trn4nsnYAg7JWE656Y7JmAIOqwmeydgCDquLDspIDsnYQg6rCA7KeA6rOgIOyDneqwge2VmOuptCDrkJjqs6AsIOyCsOyLneydgCDslYTrnpjsmYAg6rCZ64ukLgojIEthcHBhIEFncmVlbWVudAojIDwgMCBMZXNzIHRoYW4gY2hhbmNlIGFncmVlbWVudAojIDAuMDHigJMwLjIwIFNsaWdodCBhZ3JlZW1lbnQKIyAwLjIx4oCTMC40MCBGYWlyIGFncmVlbWVudAojIDAuNDHigJMwLjYwIE1vZGVyYXRlIGFncmVlbWVudAojIDAuNjHigJMwLjgwIFN1YnN0YW50aWFsIGFncmVlbWVudAojIDAuODHigJMwLjk5IEFsbW9zdCBwZXJmZWN0IGFncmVlbWVudApgYGAKIVtdKC9Vc2Vycy9DQS9Eb3dubG9hZHMva2FwcGEucG5nKQoKYGBge3J9CiMg6re465+s66m0IOyZnCBrYXBwYSDrpbwg67O064qU6rCAPwojIOyYiOulvCDrk6TslrQsIOuMgOu2gOu2hCDsi6TtjKjtlZjripQg7Iuk7KCcIOyDge2ZqeyXkCDrjIDtlbTshJwsIOyasOyXsO2VmOqyjOuPhCDrjIDrtoDrtoQg7Iuk7Yyo7ZWgIOqyg+ydtOudvOqzoCDsmIjsuKHtlZjripQg66qo64247J20IOyeiOuLpOuptCwgCiMgQWNjdXJhY3kg6rCS7J2AIOunpOyasCDrhpLsp4Drp4wsIGthcHBhIOqwkuydgCDrp6TsmrAg64Ku6rKMIOuCmOyYpOqyjCDrkKjsnYQg7JWMIOyImCDsnojri6QuIAojIGthcHBhIOuKlCDrp6TsmrAg7ZWc7Kq97Jy866GcIHNrZXcg65CY7Ja0IOyeiOuKlCBjYXRlZ29yaWNhbCB2YXIg7JeQIOuMgO2VtCDsmIjsuKHsnYQg7ZWgIOuVjCwg7Jyg7J2Y6rmK6rKMIOyCtO2OtOu0kOyVvCDtlZzri6QuICAKCnN0IDwtIGhlYWQoc3Vic2V0KHJlc3VsdCwgc3VjY2VzcyA9PSAwICYgcHJlZGljdCA9PSAwKSwgMTAwMDApCnIzIDwtIHJiaW5kKHN0LCBoZWFkKHN1YnNldChyZXN1bHQsIHN1Y2Nlc3MgPT0gMCAmIHByZWRpY3QgPT0gMSksIDEwMCkpCnIzIDwtIHJiaW5kKHIzLCBoZWFkKHN1YnNldChyZXN1bHQsIHN1Y2Nlc3MgPT0gMSAmIHByZWRpY3QgPT0gMCksIDEwMCkpCnIzIDwtIHJiaW5kKHIzLCBoZWFkKHN1YnNldChyZXN1bHQsIHN1Y2Nlc3MgPT0gMSAmIHByZWRpY3QgPT0gMSksIDIwKSkKCmNtIDwtIGNvbmZ1c2lvbk1hdHJpeChyMyRwcmVkaWN0LCByMyRzdWNjZXNzKQpwcmludChjbSRvdmVyYWxsKQpgYGAKCmBgYHtyfQojIDUuIOygge2Vqe2VnCBtZWFzdXJlbWVudCDripQg7Ja065akIOqyg+yduOqwgD8g7LyA7J207IqkIOu2hOyEnSAKYGBgCiFbXSgvVXNlcnMvQ0EvRG93bmxvYWRzL21vZGVsX3BlcmYucG5nKQoKYGBge3J9CiMgNS4xIOunpOyasCDsobDsi6zsiqTrn73qsowgZmFpbCDsvIDsnbTsiqTrpbwg7YOQ7KeA7ZWY6rOgLCBmYWlsIOydtCDsmIjsg4HrkJjripQg6rK97JqwIOuztOyImOyggeyduCDrjIDssYXsnYQg7KCc7Iuc7ZWY64qUIOqyg+ydtCDrqqntkZzrnbzrqbQgCiMgcHJlY2lzaW9uIG9mIGZhaWwg7J20IOygnOydvCDspJHsmpTtlZwg7JqU7IaM6rCAIOuQnOuLpC4gICggdGhyZXNob2xkID0gMC4xIOyEoO2DnSApCiMgNS4zIOunpOyasCDqs7XqsqnsoIHsnLzroZwgZmFpbCDsvIDsnbTsiqTrpbwg7YOQ7KeA7ZWY6rOgLCBGTiDsnbQg67Cc7IOd7ZWgIOqyveyasCByaXNrIOulvCDqsJDri7ntlbTrgrwg7IiYIOyeiOuLpOuptCwKIyByZWNhbGwgb2YgZmFpbCDsnbQg7KCc7J28IOykkeyalO2VnCDsmpTshozqsIAg65Cc64ukLiAoIHRocmVzaG9sZCA+IDAuNyDshKDtg50gKQojIDUuMiDquLgg7LC+6riwIO2RnOyngO2MkOyXkOyEnCDsmKTrpbjsqr0g7Jm87Kq97J2EIOunnuy2lOuKlCDrrLjsoJzrpbwg7ZG464qUIOqyg+ydtOudvOuptCwgCiMgYWNjdXJhY3kg7Zi57J2AIGYtbWVhc3VyZSDqsIAg6riw7KSA7J20IOuQnOuLpC4KYGBgCiFbXSgvVXNlcnMvQ0EvRG93bmxvYWRzL3NlbGVjdF9zdGQucG5nKQpgYGB7cn0KI3JlZiA6IGh0dHA6Ly93d3cuY2lyY3VsYXRpb24ub3Iua3Ivd29ya3Nob3AvMjAxNnNwcmluZy9maWxlLyVFQiU4QyU4MCVFRCU5NSU5QyVFQyU4QiVBQyVFQyU5RSVBNSVFRCU5NSU5OSVFRCU5QSU4QyUyMCVFQyVCNiU5OCVFQSVCMyU4NCVFQyU5QiU5MCVFQSVCMyVBMC9rc2MyMjYucGRmCmBgYAoKYGBge3J9CiMgNi4g7KCV66asIAojIEVEQSDsmYAg6riw67O47KCB7J24IGNsZWFuaW5nIOyXkCDtlYTsmpTtlZwg7Ya16rOE7KCBIOqzoOywsOqzvCAKIyDrqqjrjbjsnZgg6rKw6rO87JeQIOuMgO2VnCBtZWFzdXJlbWVudCDrsKnsi53qs7wg7ISg7YOd7JeQIOuMgO2VnCDtjJDri6jsnbQg6rCW7Law7KeA66m0LCAKIyDsoIHtlantlZwg6riw67KV7J2EIOywvuyVhCDsoIHsmqntlZjrqbQg65Cc64ukLiAKIyDrqqjrjbjsnYQg7Yqc64ud7ZWY6rOgIOyVmeyDgeu4lO2VmOuKlCDqs7zsoJXrj4Qg7KSR7JqU7ZWY7KeA66eMLCDqsIDsnqUg7KSR7JqU7ZWcIOqygyDshLjqsIDsp4DripQgY2xlYW5pbmcg6rO8IGZlYXR1cmUgZW5nLiDqt7jrpqzqs6Ag7KCB7KCI7ZWcIO2MkOuLqOuyleyXkCDqt7zqsbDtlZwg7J2Y7IKs6rKw7KCV7J2064ukLgpgYGAKCgo=